Traditional multitasking operating systems (e.g., UNIX, Windows) have been implemented in computing environments to provide a way to allocate the resources of the computing environment (e.g., CPU, memory, Input/Output (I/O) devices) among various user applications that may be running simultaneously in the computing environment. The operating system itself includes a number of functions (executable code) and data structures that may be used to implement the resource allocation services of the operating system. A program that performs actions may be referred to as a task (also known as a “thread”), and a collection of tasks may be referred to as a “process”. Upon loading and execution of the operating system into the computing environment, “system tasks” and “system processes” are created in order to support the resource allocation needs of the system. User applications likewise, upon execution, may cause the creation of tasks (“user tasks”) and processes (“user processes”) in order to perform the actions desired from the application.
Systems may often include shared resources that when accessed by a first task, should not be subsequently accessed by a second task until the first task's use of the resource has been completed. Examples of such shared resources may include a tape, a table in a database, a critical region in memory, etc. Operating systems may include one or more mutual exclusion control mechanisms that may be used to prevent a second task's access to such shared resources while the resources are in use by a first task. A mutual exclusion control mechanism may include functions such as disabling interrupts, preemptive locks, or mutual exclusion semaphores.
Operating systems also may include a priority control mechanism to control the execution of both system and user tasks. In a priority control mechanism, tasks may be assigned a priority value, e.g., a number ranging from a lowest priority to a highest priority. When multiple tasks contend for resources, a higher priority task generally receives more resources from the system than a lower priority task. A system including a priority control mechanism generally will not force a higher priority task to wait for a lower priority task to complete, but instead, where possible, may preempt the lower priority task until the high priority task either terminates, has its priority lowered, or stops for some other reason.
Some systems include a so-called “absolute” priority mechanism. In an “absolute” priority mechanism, lower priority tasks never preempt higher priority tasks. A higher priority task generally receives all available system resources until it completes, or until an even higher priority task interrupts the task. However, altering the control of a critical shared resource in the middle of the low priority task's use of the resource may jeopardize the integrity of the resource. For example, if the lower priority task is currently writing to a table in a database, allowing another higher priority task to write while the lower priority task's write operation is in progress may damage the integrity or consistency of the table. Therefore, mutual exclusion control mechanisms may be configured to allow a lower priority task to maintain control of a critical shared resources even when a lower priority task is preempted by higher priority tasks.
A “priority inversion” may occur when a lower priority task holds a resource that is needed by a higher priority task. FIG. 1 illustrates the effect of a priority inversion in an example system. Suppose, as shown at 102, that task C, a low priority task, is currently executing. At 104, task C takes a shared resource that is controlled with a mutual exclusion control mechanism. At 106, task A, a high priority task, preempts task C and begins to execute. At 108, task A attempts to take the resource currently held by task C. The mutual exclusion control mechanism prevents task A from accessing the resource until Task C has finished using the resource. Thus, Task A may “block”, i.e., Task A stops executing and waits to receive the resource. The system may place task A on a “wait” queue and allow other tasks to execute while the blocked task waits. Task C then begins to execute, until 110, when task C is preempted by task B, a medium priority task with priority higher than task C but lower priority than task A. At 110, the resource is still held by task C. Thus, task A is still blocked while task B executes, even though task A has a higher priority than task B and task B is not the task holding the resource for which task A is waiting. When task B finishes execution at 112, task C continues its execution until it finishes with the resource at 114. Then, task A can acquire the resource and begin executing. Effectively, while task A was blocked on the resource held by task C, task A waited for task B as if task A had the same low priority as task C. This problem is called a “priority inversion”. Priority inversion is undesirable in many applications, particularly in real-time systems which seek to guarantee the real-time performance of certain tasks.
A conventional solution to the problem of priority inversion is “priority inheritance”, i.e., raising the priority of a low priority task holding a resource needed by a higher priority task. An example of priority inheritance is illustrated in FIG. 2. Similar to the example illustrated in FIG. 1, in the example illustrated in FIG. 2, task C begins executing at 202. Task C acquires the resource at 204. Task C is preempted by high priority task A at 206. Task A attempts to take the resource, held by task C, at 208. However, when task A blocks on the resource held by task C, the current priority of task C is temporarily raised to the priority of task A, i.e., task C “inherits” the priority of task A. Thus task B does not preempt task C, and task C runs uninterrupted until it gives the resource to task A at 210. When task C has finished using the resource and gives it to task A, task C's current priority is reduced to its original base priority. When Task A acquires the resource, task A unblocks and preempts task C. Task A then runs to completion at 212. Task B does not run until after Task A has completed. A priority inversion has been avoided by using priority inheritance.
Priority inheritance has been previously implemented using various “stack” or “record” algorithms. In these algorithms, all unsatisfied requests for resources are tracked, e.g., by using a stack or other data structure with an entry for each unsatisfied resource request. The current priority of a task holding resources is raised to the priority of the highest priority task blocked on any resource held by the task. Each time a task releases a resource, e.g., by giving a semaphore, the data structure entry corresponding to the satisfied request for that resource is deleted. If a blocked task is deleted or times out, the corresponding resource request may also be deleted. Then, the current priority of the task that gave up the resource may be adjusted downward to the priority of the highest priority task still waiting to receive a resource from the task, or if no higher priority tasks are waiting, to the base priority of the task. The stack algorithm has the advantage of insuring that priority inheritance is limited, both in duration and in the priority level that is inherited. However, the stack algorithm does not use a predetermined amount of memory to track priority inheritance, i.e., the amount of memory used increases significantly as the number of resources that are held by a task increases. In addition, the stack algorithm may be computationally intensive, particularly as the number of resources that are tracked increases. Unbounded memory consumption and large computational overhead are undesirable properties, particularly in real time or embedded systems. Because priority control and mutual exclusion control mechanisms may run in the operating system kernel, the undesirability of computational overhead and unbounded memory consumption is magnified.
A conventional alternative to the stack algorithm that has been used in real time and embedded systems is the so-called “ratchet algorithm”. See, e.g., Wind River® VxWorks® Programmer's Guide Version 5.4, at p.54. In the ratchet algorithm, when a task blocks on a resource protected by a mutual exclusion control mechanism and held by a lower priority task, the resource-holding task's current priority is raised to the current priority of the resource-requesting task. The resource-holding task's priority is lowered to its base priority when the resource-holding task has released all of the resources protected by a mutual exclusion control mechanism that the resource-holding task holds. The ratchet algorithm may be implemented by maintaining a count of the number of resources protected by a mutual exclusion control mechanism that are held by a task. The count is incremented each time the task takes or acquires a resource protected by a mutual exclusion control mechanism. The count is decremented each time a resource protected by a mutual exclusion control mechanism is released. The task's priority is lowered to its base priority whenever the count of resources protected by a mutual exclusion control mechanism that are held by the task is decremented to zero.
Unlike the stack algorithm, the ratchet algorithm is computationally simple and has limited memory requirements, needing only a predetermined amount of memory for each task, i.e., a single counter variable for each task, and variables for recording each task's base and current priorities. However, in the ratchet algorithm, tasks will often retain a higher inherited priority for longer than is necessary to prevent priority inversion. This results in poor real time performance for other higher priority tasks. For example, in the example illustrated in FIG. 2 and described above, low priority task C might retain its higher inherited priority after releasing the resource at 210 if task C held another resource protected by a mutual exclusion control mechanism. The real time performance of the medium priority task B, or even possibly high priority task A, would be negatively effected if task C retained its higher inherited priority for longer than necessary.